package leetcode.p1024;

import java.util.Arrays;

/**
 * @author: trtan
 * @create: 2021-04-12 19:20
 * @description:
 **/
public class VideoStitching {
    public static void main(String[] args) {
        int[][] c = new int[][]{{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
        System.out.println(new VideoStitching().videoStitching(c, 10));
    }

    public int videoStitching(int[][] clips, int T) {
        Arrays.sort(clips, (a, b)->{
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });
        int nowR = 0;
        int result = 0;
        int i = 0;
        int l, r;
        while (i < clips.length) {
            if (nowR >= T) {
                break;
            }
            l = clips[i][0];
            r = clips[i][1];
            if (l <= nowR) {
                int tmpR = 0;
                while (i < clips.length && l <= nowR) {
                    tmpR = Math.max(tmpR, r);
                    i++;
                    if (i == clips.length) {
                        break;
                    }
                    l = clips[i][0];
                    r = clips[i][1];
                }
                nowR = Math.max(tmpR, nowR);
            } else {
                result = -1;
                break;
            }
            result++;
        }
        return nowR >= T ? result : -1;
    }
}
